package cn.bouncyslime.algorithms.stack.infixToPostfix;

import java.util.*;

/**
 * 将中缀表达式转为后缀表达式，其中表达式的操作数是数字
 * @author 张一卓
 */
public class InfixToPostfix2 {
	/**
	 * 中缀表达式字符串
	 */
	private String input;
	/**
	 * 用来存放运算符的栈
	 */
	private Deque<String> stack = new LinkedList<>();
	/**
	 * 设定运算符优先级的Map
	 */
	private Map<String, Integer> operatorPriority = new HashMap<>();
	/**
	 * 存储所有运算符的List
	 */
	private List<String> operatorList = new ArrayList<>();
	/**
	 * 将中缀表达式转换为后缀表达式的结果List
	 */
	private List<String> outputList = new ArrayList<>();
	
	/**
	 * 用来初始化运算符优先级Map{@link #operatorPriority}和存有所有运算符的List{@link #outputList}
	 * @param input 中缀表达式字符串
	 */
	public InfixToPostfix2(String input) {
		this.input = input;
		operatorPriority.put("(", 1);
		operatorPriority.put(")", 1);
		operatorPriority.put("*", 2);
		operatorPriority.put("/", 2);
		operatorPriority.put("+", 3);
		operatorPriority.put("-", 3);
		operatorList.add("(");
		operatorList.add(")");
		operatorList.add("+");
		operatorList.add("-");
		operatorList.add("*");
		operatorList.add("/");
	}
	
	/**
	 * 用来将中缀表达式转换为后缀表达式，转换的结果为存储所有字符的List，之后将该List转换为数组输出
	 * @return 存储有后缀表达式各个字符的char数组
	 */
	public String[] change() {
		String[] inputSplit = input.split(" ");
		for (int i = 0; i < inputSplit.length; i++) {
			// 如果输入字符不是运算符
			if (!operatorList.contains(inputSplit[i])) {
				outputList.add(inputSplit[i]);
			// 输入字符是运算符
			}else {
				// 运算符栈是否为空栈
				if (stack.isEmpty()) {
					stack.push(inputSplit[i]);
				}else {
					if (!inputSplit[i].equals(")")) {
						// 当压入栈的运算符的优先级比前面的运算符等级低或者相等，则将前面的运算符抛出栈并存放到后缀表达式List中，如果压入栈的运算符还是比再前面的运算符优先级低或者相等，则会再次执行
						while (!stack.isEmpty() && operatorPriority.get(stack.peek())!=1 && operatorPriority.get(inputSplit[i])>=operatorPriority.get(stack.peek())) {
							outputList.add(stack.pop());
						}
						// 排除了运算符优先级不小于自己的运算符之后将自己压入栈
						stack.push(inputSplit[i]);
					// 如果碰到闭括号
					}else {
						// 抛出栈中开括号之前的元素，括号不做输出
						while (!stack.peek().equals("(")) {
							outputList.add(stack.pop());
						}
						stack.pop();
					}
				}
			}
			// 遍历到输入字符串截尾之后，如果栈中还有元素则
			while (i == inputSplit.length-1 && !stack.isEmpty()) {
				outputList.add(stack.pop());
			}
		}
		return outputList.toArray(new String[0]);
	}
	
	public static void main(String[] args) {
		String input = "3.6 + 6 * 2.1 + ( 8 * 1.2 + 2 )";
		InfixToPostfix2 infixToPostfix = new InfixToPostfix2(input);
		System.out.println(Arrays.toString(infixToPostfix.change()));
	}
}
